//Convert a non-negative integer num to its English words representation. 
//
// 
// Example 1: 
// Input: num = 123
//Output: "One Hundred Twenty Three"
// Example 2: 
// Input: num = 12345
//Output: "Twelve Thousand Three Hundred Forty Five"
// Example 3: 
// Input: num = 1234567
//Output: "One Million Two Hundred Thirty Four Thousand Five Hundred Sixty Seven
//"
// Example 4: 
// Input: num = 1234567891

//Output: "One Billion Two Hundred Thirty Four Million Five Hundred Sixty Seven 
//Thousand Eight Hundred Ninety One"
// 
// 
// Constraints: 
//
// 
// 0 <= num <= 231 - 1 
// 
// Related Topics 递归 数学 字符串 
// 👍 242 👎 0


package leetcode.editor.cn;

import java.util.LinkedList;
import java.util.List;
import java.util.stream.Collectors;

//Java：Integer to English Words
class P273IntegerToEnglishWords {
    public static void main(String[] args) {
        Solution solution = new P273IntegerToEnglishWords().new Solution();
        System.out.println(solution.numberToWords(100000));

        // TO TEST
    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        String[] oneDigit = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine", "Ten",
                "Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen", "Twenty"};
        String[] other = {"Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
        String[] nameArr = {"Ten", "Hundred", "Thousand", "Million", "Billion"};
        int[] valueArr = {10, 100, 1000, 1000 * 1000, 1000 * 1000 * 1000};


        public String numberToWords(int num) {
            List<String> stringBuilder = new LinkedList<>();
            if (num == 0) {
                return "Zero";
            }
            word(num, stringBuilder);

            return stringBuilder.stream().collect(Collectors.joining(" ", "", ""));
        }

        public void word(int num, List<String> total) {

            //小于10，one two,
            //小于100，用twenty,twelve
            //小于1000，用hundred，1000
            //小于10000000，用million，1000 * 1000 * 10
            //小于10000000000，用billion，1000*1000*1000
            if (num == 0) {
                return;
            }
            if (1 <= num && num < 100) {
                if (num <= 20) {
                    total.add(oneDigit[num - 1]);
                } else {
                    if (num % 10 == 0) {
                        total.add(other[num / 10 - 2]);
                    } else {
                        total.add(other[num / 10 - 2]);
                        total.add(oneDigit[num % 10 - 1]);
                    }
                }
                return;
            }

            for (int i = valueArr.length - 1; i >= 0; i--) {
                String name = nameArr[i];
                int value = valueArr[i];
                int left = num / value;
                int right = num % value;
                if (left > 0) {
                    word(left, total);
                    total.add(name);
                    word(right, total);
                    break;
                } else {
                    continue;
                }

            }
        }

//        public String numberToWords(int num) {
//            List<String> stringBuilder = new LinkedList<>();
//            if (num == 0) {
//                return "Zero";
//            }
//            word(num, stringBuilder);
//
//            return stringBuilder.stream().collect(Collectors.joining(" ", "", ""));
//        }
//
//        public void word(int num, List<String> total) {
//
//            //小于10，one two,
//            //小于100，用twenty,twelve
//            //小于1000，用hundred，1000
//            //小于10000000，用million，1000 * 1000 * 10
//            //小于10000000000，用billion，1000*1000*1000
//            if (num == 0) {
//                return;
//            }
//            if (1 <= num && num < 100) {
//                if (num <= 20) {
//                    total.add(oneDigit[num - 1]);
//                } else {
//                    if (num % 10 == 0) {
//                        total.add(other[num / 10 - 2]);
//                    } else {
//                        total.add(other[num / 10 - 2]);
//                        total.add(oneDigit[num % 10 - 1]);
//                    }
//                }
//                return;
//            }
//
//            for (int i = valueArr.length - 1; i >= 0; i--) {
//                String name = nameArr[i];
//                int value = valueArr[i];
//                int left = num / value;
//                int right = num % value;
//                if (left > 0) {
//                    word(left, total);
//                    total.add(name);
//                    word(right, total);
//                    break;
//                } else {
//                    continue;
//                }
//
//            }
//        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}